package com.xyhuo.leetcode.january;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 子集Ⅱ
 * https://leetcode.cn/problems/subsets-ii/
 *
 * @time 2024/1/2
 */
public class SubsetsWithDup {

//    public static void main(String[] args) {
//        SubsetsWithDup swd = new SubsetsWithDup();
//        int[] nums = {1, 2, 2};
//        swd.subsetsWithDup(nums);
//    }


    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>>[] dp = new List[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = new ArrayList<>();
        }
        List<Integer> firstItem = new ArrayList<>();
        firstItem.add(nums[0]);
        dp[0].add(firstItem);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                for (List<Integer> list : dp[i - 1]) {
                    List<Integer> newList = new ArrayList<>();
                    newList.addAll(list);
                    newList.add(nums[i]);
                    dp[i].add(newList);
                }
                continue;
            }

            for (int j = 0; j <= i - 1; j++) {
                for (List<Integer> list : dp[j]) {
                    List<Integer> newList = new ArrayList<>();
                    newList.addAll(list);
                    newList.add(nums[i]);
                    dp[i].add(newList);
                }
            }
            List<Integer> onlyCurNumList = new ArrayList<>();
            onlyCurNumList.add(nums[i]);
            dp[i].add(onlyCurNumList);
        }
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> zero = new ArrayList<>();
        ans.add(zero);
        for (int i = 0; i < nums.length; i++) {
            ans.addAll(dp[i]);
        }
        return ans;
    }
}
